package com.chixing.day02;



/**
 * 排序工具类
 * 提供了常用的排序算法:冒泡排序,快速排序.....
 */
public class SortUtil {
    /**
     * 冒泡排序
     *
     * @param original 要排序的原始数组
     * @return 返回排好序的数组
     */
    public static int[] bubbleSort(int[] original) {
        for (int i = 0; i < original.length - 1; i++) {
            for (int j = 0; j < original.length - i - 1; j++) {
                if (original[j] > original[j + 1]) {
                    int temp = original[j];
                    original[j] = original[j + 1];
                    original[j + 1] = temp;
                }
            }
        }
        return original;
    }



    /**
     * 快速排序
     * 获得基础的下标
     *
     * @param arr  需要排序的数组
     * @param low  数组待排序的最小的下标
     * @param high 数组待排序的最大的下标
     * @return 返回中轴值（该值大于左边值,小于右边值）
     */
    public static  int getMiddle(int[] arr,int low,int high){
        int temp = arr[low];// temp = 67
        while(low < high){// 0<1
            while(low < high && arr[high] > temp){//0<1  && 14>12
                high--;//h  = 0
            }
            arr[low] = arr[high]; // a[0] = a[0];
            while(low < high && arr[low] <= temp){//
                low++;
            }
            arr[high] = arr[low];//a[0] = a[0]
        }
        arr[low] = temp;//a[0] = 12
        return low;// 8
    }
    public  static void quickSort(int[] arr,int low, int high){
        if(low < high){//0,1
            //将数组一份为二
            int middle = getMiddle(arr, low, high);// arr 0,9  m = 8

            //System.out.println("middle = " + middle);//m =4
            //左边进行递归 快速排序
            quickSort(arr,low,middle -1);  // arr 0,7
            //右边进行递归 快速排序
            quickSort(arr, middle + 1, high);// arr 9,9
        }
    }
}



